package LinearList;
//带头单链表【虚拟头节点】
public class SingleLinkedListWithHead {
    //当前存储的元素个数
    private int size;
    //虚拟头节点[只作为头部，不存储元素]
    private Node DummyHead=new Node(-1);

    /**
     * 1.在index位置插入元素val.此时有虚拟头节点，不用再单独考虑index==0情况
     * @param index
     * @param val
     */
    public void addIndex(int index,int val){
        //1.判断合法性
        if(index<0||index>size){
            System.err.println("add index illegal");
            return;
        }
        //2.所有插入节点全是中间节点【头节点不再是特殊情况了】
        Node node=new Node(val);
        //找到待插入节点的前驱
        Node prev=DummyHead;
        for (int i = 0; i < index; i++) {
            prev=prev.next;
        }
        //循环走完prev已经指向了待插入位置的前驱
        node.next=prev.next;
        prev.next=node;
        size++;
    }
    //头节点插入
    public void addFirst(int val){
        addIndex(0,val);
    }
    //尾节点插入
    public void addLast(int val){
        addIndex(size,val);
    }

    /**
     * 删除index节点的元素
     * @param index
     */
    public void removeIndex(int index){
        //1.合法性
        if(index<0||index>=size){
            System.err.println("remove index illegal");
            return;
        }
        //2.删除中间节点
        Node prev=DummyHead;//1）找前驱，从虚拟头节点开始遍历
        for (int i = 0; i < index; i++) {//走到前驱位置
            prev=prev.next;
        }
        //2）删除操作
        //prev.next=prev.next.next;
        Node cur=prev.next;
        prev.next=cur.next;
        cur.next=null;
        size--;
    }

    /**
     * 打印链表
     * @return
     */
    public String toString(){
        Node node=DummyHead.next;
        String ret="";
        while(node!=null){
            ret+=node.val;
            ret+="->";
            node=node.next;
        }
        ret+="NULL";
        return ret;
    }
}

